package com.study.concurrentprogramming.AQSStudy;

import sun.misc.Unsafe;

import java.util.concurrent.locks.AbstractOwnableSynchronizer;
import java.util.concurrent.locks.AbstractQueuedSynchronizer;
import java.util.concurrent.locks.LockSupport;

public class AQS extends AbstractOwnableSynchronizer {
    protected AQS() {
    }

    static final class Node {
        // 标记一种节点等待在共享模式
        static final Node SHARE = new Node();

        // 标记一个节点等待在独占模式
        static final Node EXCLUSIVE = null;

        // 等待状态, 表明线程已经取消
        static final int CANCELLED = 1;

        // 等待状态，表明后继的线程需要恢复
        static final int SIGNAL = -1;

        // 等待状态，表明线程正在条件上等待
        static final int CONDITION = -2;

        // 等待状态，表明下一个需要共享的线程必须无条件的传导
        static final int PROPAGATE = -3;

        // 等待状态，通过CAS方式读取
        volatile int waitStatus;

        // 连接到当前节点的前置节点
        volatile Node prev;

        // 连接到当前节点的后继节点
        volatile Node next;

        // 绑定当前节点的线程
        volatile Thread thread;

        // 连接下一个节点：等待在条件上的或者一个特殊的共享值。
        Node nextWaiter;

        // 返回节点是否等待在共享模式
        final boolean isShared() {
            return nextWaiter == SHARE;
        }

        // 返回前置节点
        final Node predecessor() {
            Node p = prev;
            if (p == null) {
                throw new NullPointerException();
            } else {
                return p;
            }
        }

        Node() {
        }

        // Used by addWaiter
        Node(Thread thread, Node mode) {
            this.nextWaiter = mode;
            this.thread = thread;
        }

        // Used by Condition
        Node(Thread thread, int waitStatus) {
            this.waitStatus = waitStatus;
            this.thread = thread;
        }
    }

    // 等待队列的头节点，使用懒加载
    private transient volatile Node head;

    // 等待队列的尾节点，使用懒加载
    private transient volatile Node tail;

    // 同步状态
    private volatile int state;

    protected final int getState() {
        return state;
    }

    protected final void setState(int newState) {
        state = newState;
    }

    protected final boolean compareAndSetState(int expect, int update) {
        // See below for intrinsics setup to support this
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }

    // 自旋超时阈值（单位：纳秒)，1000L ns内，自旋比超时等待更快，一个简单的评估可以有效的提高超时响应速度
    static final long spinForTimeoutThreshold = 1000L;

    /**
     * 插入节点
     *
     * @param node 待插入的节点
     * @return 返回插入节点的前一个节点
     */
    private Node enq(final Node node) {
        for (; ; ) {
            Node t = tail;
            if (t == null) {
                if (compareAndSetHead(new Node())) {
                    tail = head;
                }
            } else {
                node.prev = t;
                if (compareAndSetTail(t, node)) {
                    // 只会有一个线程进入
                    t.next = node;
                    return t;
                }
            }
        }
    }


    /**
     * Creates and enqueues node for current thread and given mode.
     *
     * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
     * @return the new node
     */
    private AQS.Node addWaiter(AQS.Node mode) {
        AQS.Node node = new AQS.Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        AQS.Node pred = tail;
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }


    /**
     * Wakes up node's successor, if one exists.
     *
     * @param node the node
     */
    private void unparkSuccessor(AQS.Node node) {
        /*
         * If status is negative (i.e., possibly needing signal) try
         * to clear in anticipation of signalling.  It is OK if this
         * fails or if status is changed by waiting thread.
         */
        int ws = node.waitStatus;
        if (ws < 0)
            compareAndSetWaitStatus(node, ws, 0);

        /*
         * Thread to unpark is held in successor, which is normally
         * just the next node.  But if cancelled or apparently null,
         * traverse backwards from tail to find the actual
         * non-cancelled successor.
         */
        AQS.Node s = node.next;
        if (s == null || s.waitStatus > 0) {
            s = null;
            for (AQS.Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0)
                    s = t;
        }
        if (s != null)
            LockSupport.unpark(s.thread);
    }


    /**
     * Sets head of queue to be node, thus dequeuing. Called only by
     * acquire methods.  Also nulls out unused fields for sake of GC
     * and to suppress unnecessary signals and traversals.
     *
     * @param node the node
     */
    private void setHead(AQS.Node node) {
        head = node;
        node.thread = null;
        node.prev = null;
    }


    /**
     * Release action for shared mode -- signals successor and ensures
     * propagation. (Note: For exclusive mode, release just amounts
     * to calling unparkSuccessor of head if it needs signal.)
     */
    private void doReleaseShared() {
        for (; ; ) {
            AQS.Node h = head;
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                if (ws == AQS.Node.SIGNAL) {
                    if (!compareAndSetWaitStatus(h, AQS.Node.SIGNAL, 0))
                        continue;            // loop to recheck cases
                    unparkSuccessor(h);
                } else if (ws == 0 &&
                        !compareAndSetWaitStatus(h, 0, AQS.Node.PROPAGATE))
                    continue;                // loop on failed CAS
            }
            if (h == head)                   // loop if head changed
                break;
        }
    }

    private void setHeadAndPropagate(AQS.Node node, int propagate) {
        AQS.Node h = head; // Record old head for check below
        setHead(node);
        if (propagate > 0 || h == null || h.waitStatus < 0 ||
                (h = head) == null || h.waitStatus < 0) {
            AQS.Node s = node.next;
            if (s == null || s.isShared())
                doReleaseShared();
        }
    }

    private void cancelAcquire(AQS.Node node) {
        // Ignore if node doesn't exist
        if (node == null)
            return;

        node.thread = null;

        // Skip cancelled predecessors
        AQS.Node pred = node.prev;
        while (pred.waitStatus > 0)
            node.prev = pred = pred.prev;

        AQS.Node predNext = pred.next;

        node.waitStatus = AQS.Node.CANCELLED;

        // If we are the tail, remove ourselves.
        if (node == tail && compareAndSetTail(node, pred)) {
            compareAndSetNext(pred, predNext, null);
        } else {
            int ws;
            if (pred != head &&
                    ((ws = pred.waitStatus) == AQS.Node.SIGNAL ||
                            (ws <= 0 && compareAndSetWaitStatus(pred, ws, AQS.Node.SIGNAL))) &&
                    pred.thread != null) {
                AQS.Node next = node.next;
                if (next != null && next.waitStatus <= 0)
                    compareAndSetNext(pred, predNext, next);
            } else {
                unparkSuccessor(node);
            }

            node.next = node; // help GC
        }
    }

    private static boolean shouldParkAfterFailedAcquire(AQS.Node pred, AQS.Node node) {
        int ws = pred.waitStatus;
        if (ws == AQS.Node.SIGNAL)
            return true;
        if (ws > 0) {
            do {
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);
            pred.next = node;
        } else {
            compareAndSetWaitStatus(pred, ws, AQS.Node.SIGNAL);
        }
        return false;
    }

    static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }

    private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
    }

    final boolean acquireQueued(final AQS.Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final AQS.Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    private void doAcquireInterruptibly(int arg)
            throws InterruptedException {
        final AQS.Node node = addWaiter(AQS.Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (;;) {
                final AQS.Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    private boolean doAcquireNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (nanosTimeout <= 0L)
            return false;
        final long deadline = System.nanoTime() + nanosTimeout;
        final AQS.Node node = addWaiter(AQS.Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (;;) {
                final AQS.Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return true;
                }
                nanosTimeout = deadline - System.nanoTime();
                if (nanosTimeout <= 0L)
                    return false;
                if (shouldParkAfterFailedAcquire(p, node) &&
                        nanosTimeout > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if (Thread.interrupted())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }


    protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException();
    }

    // 用来支持CAS操作
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long stateOffset;
    private static final long headOffset;
    private static final long tailOffset;
    private static final long waitStatusOffset;
    private static final long nextOffset;


    static {
        try {
            stateOffset = unsafe.objectFieldOffset
                    (AQS.class.getDeclaredField("state"));
            headOffset = unsafe.objectFieldOffset
                    (AQS.class.getDeclaredField("head"));
            tailOffset = unsafe.objectFieldOffset
                    (AQS.class.getDeclaredField("tail"));
            waitStatusOffset = unsafe.objectFieldOffset
                    (AQS.Node.class.getDeclaredField("waitStatus"));
            nextOffset = unsafe.objectFieldOffset
                    (AQS.Node.class.getDeclaredField("next"));

        } catch (Exception ex) {
            throw new Error(ex);
        }
    }

    /**
     * CAS head field. Used only by enq.
     */
    private final boolean compareAndSetHead(AQS.Node update) {
        return unsafe.compareAndSwapObject(this, headOffset, null, update);
    }

    /**
     * CAS tail field. Used only by enq.
     */
    private final boolean compareAndSetTail(AQS.Node expect, AQS.Node update) {
        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
    }


    /**
     * CAS waitStatus field of a node.
     */
    private static final boolean compareAndSetWaitStatus(AQS.Node node,
                                                         int expect,
                                                         int update) {
        return unsafe.compareAndSwapInt(node, waitStatusOffset,
                expect, update);
    }

    private static final boolean compareAndSetNext(AQS.Node node,
                                                   AQS.Node expect,
                                                   AQS.Node update) {
        return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
    }
}
